package uestc.lj.advanced.dp;

/**
 * @Author:Crazlee
 * @Date:2021/12/10
 */
public class Code04_LongestCommonSubString {

	/**
	 * 两个子串的最长公共子串
	 *
	 * @param str1 子串1
	 * @param str2 子串2
	 * @return 最长公共子串
	 */
	public static String lcst1(String str1, String str2) {
		if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
			return "";
		}
		char[] charArray1 = str1.toCharArray();
		char[] charArray2 = str2.toCharArray();
		int[][] dp = getdp(charArray1, charArray2);
		int end = 0;
		int max = 0;
		for (int i = 0; i < charArray1.length; i++) {
			for (int j = 0; j < charArray2.length; j++) {
				if (dp[i][j] > max) {
					max = dp[i][j];
					end = i;
				}
			}
		}
		return str1.substring(end - max + 1, end + 1);
	}

	/**
	 * 求两个子串的最长公共子串
	 * dp[i][j]表示子串1以i结尾，子串2以j结尾的最长公共子串的长度
	 *
	 * @param charArray1 子串1
	 * @param charArray2 子串2
	 * @return dp二维数组表
	 */
	private static int[][] getdp(char[] charArray1, char[] charArray2) {
		int[][] dp = new int[charArray1.length][charArray2.length];
		for (int i = 0; i < charArray1.length; i++) {
			if (charArray1[i] == charArray2[0]) {
				dp[i][0] = 1;
			}
		}

		for (int i = 1; i < charArray2.length; i++) {
			if (charArray1[0] == charArray2[i]) {
				dp[0][i] = 1;
			}
		}

		for (int i = 1; i < charArray1.length; i++) {
			for (int j = 1; j < charArray2.length; j++) {
				if (charArray1[i] == charArray2[j]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
			}
		}
		return dp;
	}


	//==========================================================================

	public static String lcst2(String str1, String str2) {
		if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
			return "";
		}
		char[] charArray1 = str1.toCharArray();
		char[] charArray2 = str2.toCharArray();

		// 从矩阵的右上角开始计算
		int row = 0;
		int col = charArray2.length - 1;

		int max = 0;
		int end = 0;

		while (row < charArray1.length) {
			int i = row;
			int j = col;
			int len = 0;
			while (i < charArray1.length && j < charArray2.length) {
				if (charArray1[i] != charArray2[j]) {
					len = 0;
				} else {
					len++;
				}
				if (len > max) {
					end = i;
					max = len;
				}
				i++;
				j++;
			}
			if (col > 0) {
				col--;
			} else {
				row++;
			}
		}
		return str1.substring(end - max + 1, end + 1);
	}


	public static void main(String[] args) {
		String str1 = "ABC1234567DEFG";
		String str2 = "HIJKL1234567MNOP";
		System.out.println(lcst1(str1, str2));
		System.out.println(lcst2(str1, str2));

	}
}
